package binary_tree;

import java.util.*;

/**
 * @author macy
 * @date 2025/5/14 10:23
 */
public class BaseTreeDemo {

    /**
     * 前序遍历
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private static void traverse(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 访问根节点
        result.add(node.val);
        // 遍历左子树
        traverse(node.left, result);
        // 遍历右子树
        traverse(node.right, result);
    }


    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p= root;

        while (p != null || !stack.isEmpty()) {
            // 前序遍历，所以先保存结果
            while (p != null){
                list.add(p.val);
                stack.push(p);
                p = p.left;
            }
            // pop出栈顶元素
            if(!stack.isEmpty()){
                TreeNode pop = stack.pop();
                p = pop.right;

            }
        }
        return list;
    }


    /**
     * 二叉树的所有路径
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {
        StringBuilder path = new StringBuilder();
        List<String> paths = new LinkedList<>();
        dfs(root, path, paths);
        return paths;

    }

    public static void dfs(TreeNode p, StringBuilder path, List<String> paths) {
        if (p == null) {
            return;
        }
        path.append(p.val);
        // 当前节点是叶子节点
        if (p.left == null && p.right == null) {
            // 把路径加入结果
            paths.add(path.toString());
        } else {
            path.append("->");
            // 这里需要复制创建新的StringBuilder对象
            dfs(p.left, new StringBuilder(path), paths);
            dfs(p.right, new StringBuilder(path), paths);
        }
    }


    /**
     * 二叉树的层序遍历
     * @param root
     * @return
     */
    public static void levelOrderPrintByLevel(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            System.out.println();  // 每层换行
        }
    }


    /**
     * 验证二叉树
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * 其左子树中所有节点的值都 小于 node 的值。
     * 其右子树中所有节点的值都 大于 node 的值。
     * 左右子树本身也必须分别是有效的二叉搜索树
     * DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过参数传入，后者一般递归返回结果最后合并
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return divideAndConquer(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean divideAndConquer(TreeNode p, long min, long max) {
        if (p == null) {
            return true;
        }

        // 返回条件
        if (p.val <= min || max <= p.val) {
            return false;
        }
        // 分治(Divide)
        boolean left = divideAndConquer(p.left, min, p.val);
        boolean right = divideAndConquer(p.right, p.val, max);
        // 合并结果(Conquer)
        return left && right;
    }


    /**
     * 二叉树的公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
     * 分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // check
        if (root == null) {
            return null;
        }
        // 相等 直接返回root节点即可
        if (root == p || root == q) {
            return root;
        }
        // Divide
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // Conquer
        // 左右两边都不为空，则根节点为祖先
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }


    /**
     * 判断路径和 是否等于某个值
     * 路径和定义为从 root 到 leaf 的所有节点的和。
     * @param root
     * @param sum 22
     * @return true
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \      \
     *         7    2      1
     */
    public static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }


    /**
     * 统计路径和等于一个数的路径数量
     * 路径不一定以 root 开头，也不一定以 leaf 结尾，但是必须连续
     * @param root
     * @param sum
     * @return
     *
     *       10
     *      /  \
     *     5   -3
     *    / \    \
     *   3   2   11
     *  / \   \
     * 3  -2   1
     *
     * Return 3. The paths that sum to 8 are:
     *
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3. -3 -> 11
     */
    public int pathSum(TreeNode root, int sum) {
        if (root == null){
            return 0;
        }
        int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        return ret;
    }

    private int pathSumStartWithRoot(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        if (root.val == sum) {
            ret++;
        }
        ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
        return ret;
    }

    public static void main(String[] args) {
        // 构建一个示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        List<Integer> preorderResult = preorderTraversal(root);
        System.out.println("前序遍历结果: " + preorderResult);

        List<String> paths = binaryTreePaths(root);
        System.out.println("二叉树路径: " + paths);

        levelOrderPrintByLevel(root);

        System.out.println(hasPathSum(root, 10));
    }



}
